package Algorithm.LinkedListProblem;

import java.util.LinkedList;
import java.util.Queue;

/**
 * @Author cj
 * @Date 2022/1/6 20:38
 */
public class convert {

    static class Node {
        public int value;
        public Node left;
        public Node right;

        public Node(int val) {
            this.value = val;
        }
    }

    // 中序遍历，入队，拼链表
    public static Node convert1(Node head) {
        Queue<Node> queue = new LinkedList<>();
        inorder(head, queue);
        if (queue.isEmpty()) {
            return head;
        }
        head = queue.poll();
        Node pre = head, cur = null;
        pre.left = null;
        while (!queue.isEmpty()) {
            cur = queue.poll();
            pre.right = cur;
            cur.left = pre;
            pre = cur;
        }
        pre.right = null;
        return head;
    }

    public static void inorder(Node head, Queue<Node> queue) {
        if (head == null) {
            return;
        }
        inorder(head.left, queue);
        queue.offer(head);
        inorder(head.right, queue);
    }

    // 递归
    public static Node convert2(Node head) {
        if (head == null) {
            return head;
        }
        return process(head).start;
    }

    static class ReturnType {
        public Node start;
        public Node end;

        public ReturnType(Node start, Node end) {
            this.start = start;
            this.end = end;
        }
    }

    public static ReturnType process(Node head) {
        if (head == null) {
            return new ReturnType(null, null);
        }
        ReturnType leftList = process(head.left);
        if (leftList.end != null) {
            leftList.end.right = head;
        }
        head.left = leftList.end;
        ReturnType rightList = process(head.right);
        if (rightList.start != null) {
            rightList.start.left = head;
        }
        head.right = rightList.start;
        return new ReturnType(head.left == null ? head : leftList.start,
                head.right == null ? head : rightList.end);
    }

}
